package com.algorithm.thePrimaryAlgorithm;

import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.Stack;

class ListNode23 {
    int val;
    ListNode23 next;

    ListNode23() {
    }

    ListNode23(int val) {
        this.val = val;
    }

    ListNode23(int val, ListNode23 next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 递归 翻转
 */
@Slf4j
public class LinkSulotionLC23 {
    public ListNode23 reverseList(ListNode23 head) {
        if (head == null) {
            return null;
        }
        ListNode23 head1 = head;
        int lenght = 0;
        while (head1 != null) {
            lenght++;
            head1 = head1.next;
        }
        ListNode23 newHead = null;

        ListNode23 rever = rever(head, newHead, lenght);

        return rever;
    }

    private ListNode23 rever(ListNode23 head, ListNode23 ha, int lenght) {

        ListNode23 last = head;
        int index = lenght;
        while (index - 1 > 0) {
            last = last.next;
            index--;
        }
        last.next = null;
        ListNode23 newHead = ha;
        if (ha == null) {
            ha = last;
        } else {
            while (newHead.next != null) {
                newHead = newHead.next;
            }
            newHead.next = last;
        }
        if (lenght - 1 > 0) {
            lenght--;
            rever(head, ha, lenght);
        }
        return ha;

    }


    @Test
    public void test() {
        ListNode23 l1 = new ListNode23(1);
        ListNode23 l2 = new ListNode23(2);
        ListNode23 l3 = new ListNode23(3);
        ListNode23 l4 = new ListNode23(4);
        ListNode23 l5 = new ListNode23(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        reverseList(l1);
        log.info("this is test {}");
    }

    /**
     * 使用堆栈  翻转
     *
     * @param head
     * @return
     */
    public ListNode23 reverseList1(ListNode23 head) {
        if (head == null) {
            return null;
        }
        Stack<ListNode23> stack = new Stack<>();
        ListNode23 tmp = head;
        while (tmp != null) {
            stack.push(tmp);
            tmp = tmp.next;
        }

        ListNode23 result = stack.pop();
        while (!stack.isEmpty()) {
            ListNode23 pop = stack.pop();
            pop.next = null;
            ListNode23 rtmp = result;
            while (rtmp.next != null) {
                rtmp = rtmp.next;
            }
            rtmp.next = pop;

        }

        return result;
    }


    @Test
    public void test1() {
        ListNode23 l1 = new ListNode23(1);
        ListNode23 l2 = new ListNode23(2);
        ListNode23 l3 = new ListNode23(3);
        ListNode23 l4 = new ListNode23(4);
        ListNode23 l5 = new ListNode23(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        reverseList1(l1);
        log.info("this is test {}");
    }

    /**
     * 初始化一个新链表 N 每次从 原列表头部取一个结点 A  让  A.next = N 然后循环
     *
     * @param head
     * @return
     */
    public ListNode23 reverseList2(ListNode23 head) {
        ListNode23 newLink = null;
        while (head != null) {
            // 将除过头结点的 链表赋值给临时链表
            ListNode23 tmp = head.next;
            // 将头结点的下一个指向新的链表
            head.next = newLink;
            // 将头结点赋值给 新链表
            newLink = head;
            // 将临时链表 赋值
            head = tmp;

        }
        return newLink;
    }

    @Test
    public void test2() {
        ListNode23 l1 = new ListNode23(1);
        ListNode23 l2 = new ListNode23(2);
        ListNode23 l3 = new ListNode23(3);
        ListNode23 l4 = new ListNode23(4);
        ListNode23 l5 = new ListNode23(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

        reverseList2(l1);
    }
}
